package ffte.algorithm

import breeze.math.Complex

/**
 * Miscellaneous FFT utilities and mathematical functions
 *
 * This object provides fundamental mathematical utilities and reference implementations
 * for FFT algorithm development and validation. These functions serve as the
 * mathematical foundation for twiddle factor generation, DFT computations, and
 * various bit manipulation operations required throughout the FFT system.
 *
 * Key Utilities:
 * - Twiddle factor generation for complex exponentials
 * - Reference DFT/IDFT implementations for validation
 * - Mathematical utilities for bit width calculations and power operations
 * - Support functions for algorithm development and testing
 *
 * Usage Context:
 * - Twiddle factor generation in FFT cores and rotators
 * - Reference implementations for algorithm verification
 * - Mathematical utilities throughout the FFT system
 * - Test vector generation and validation
 */
object FFTMisc {

    /**
     * Twiddle factor generator
     *
     * Generates complex twiddle factors of the form W_n^k = e^(-j*2π*k/n)
     * which are essential for Cooley-Tukey FFT algorithms and other
     * transform computations.
     *
     * Mathematical Definition:
     * W_n^k = cos(2π*k/n) - j*sin(2π*k/n)
     *
     * @param k Twiddle factor index (0 ≤ k < n)
     * @param n Transform size (radix)
     * @return Complex twiddle factor W_n^k
     */
    def wnk(k:Int, n:Int) = Complex(Math.cos(2*Math.PI*k/n),-Math.sin(2*Math.PI*k/n))

    /**
     * Discrete Fourier Transform (List version)
     *
     * Reference implementation of the DFT using the direct definition.
     * This function computes the DFT using O(N²) operations and serves
     * as a reference for validating optimized FFT implementations.
     *
     * Mathematical Definition:
     * X[k] = Σ_{n=0}^{N-1} x[n] * W_N^{k*n}
     * where W_N = e^(-j*2π/N)
     *
     * @param x Input sequence as List[Complex]
     * @return DFT result as List[Complex]
     */
    def dft(x:List[Complex]) = {
		val n = x.length
		(0 until n).map{i => x.zipWithIndex.map{ case (a,k) => a*wnk(i*k,n)}.sum}.toList
	}

    /**
     * Inverse Discrete Fourier Transform (List version)
     *
     * Reference implementation of the IDFT using the direct definition.
     * This function computes the inverse DFT and serves as a reference
     * for validating optimized IFFT implementations.
     *
     * Mathematical Definition:
     * x[n] = (1/N) * Σ_{k=0}^{N-1} X[k] * W_N^{-k*n}
     * where W_N = e^(-j*2π/N)
     *
     * Note: This implementation does not include the 1/N scaling factor.
     * Scaling should be applied separately as needed.
     *
     * @param x Input frequency domain sequence as List[Complex]
     * @return IDFT result as List[Complex]
     */
    def idft(x:List[Complex]) = {
		val n = x.length
		(0 until n).map{i => x.zipWithIndex.map{ case (a,k) => a*wnk(-i*k,n)}.sum}.toList
	}

    /**
     * Discrete Fourier Transform (Array version)
     *
     * Array-based implementation of the DFT for improved performance
     * when working with mutable collections. Provides the same mathematical
     * functionality as the List version with better memory efficiency.
     *
     * @param x Input sequence as Array[Complex]
     * @return DFT result as Array[Complex]
     */
    def dft(x:Array[Complex]) = {
		val n = x.length
		(0 until n).map{i => x.zipWithIndex.map{ case (a,k) => a*wnk(i*k,n)}.sum}.toArray
	}

    /**
     * Inverse Discrete Fourier Transform (Array version)
     *
     * Array-based implementation of the IDFT for improved performance
     * when working with mutable collections. Provides the same mathematical
     * functionality as the List version with better memory efficiency.
     *
     * @param x Input frequency domain sequence as Array[Complex]
     * @return IDFT result as Array[Complex]
     */
    def idft(x:Array[Complex]) = {
		val n = x.length
		(0 until n).map{i => x.zipWithIndex.map{ case (a,k) => a*wnk(-i*k,n)}.sum}.toArray
	}

    /**
     * Integer power calculation
     *
     * Computes integer powers using recursive multiplication.
     * This utility function is used for various mathematical calculations
     * throughout the FFT system, particularly in bit width and
     * address calculations.
     *
     * @param n Base integer
     * @param k Exponent (non-negative)
     * @return n^k as BigInt
     */
    def pow(n:Int,k:Int):BigInt = if(k==0) 1 else n*pow(n,k-1)

    /**
     * Log base 2 ceiling calculation utility
     *
     * Computes the ceiling of log base 2 for a given positive integer.
     * This is essential for calculating bit widths required to represent
     * addresses, indices, and other quantities in hardware implementations.
     *
     * Mathematical Definition:
     * result = ⌈log₂(value)⌉
     * which is equivalent to the number of bits needed to represent (value-1)
     *
     * Usage Examples:
     * - log2Up(1) = 0 (1 bit needed for value 0)
     * - log2Up(2) = 1 (1 bit needed for values 0-1)
     * - log2Up(3) = 2 (2 bits needed for values 0-2)
     * - log2Up(8) = 3 (3 bits needed for values 0-7)
     * - log2Up(9) = 4 (4 bits needed for values 0-8)
     *
     * Applications:
     * - Address width calculation for memories
     * - Counter bit width determination
     * - Index bit width specification
     * - Resource sizing in hardware generation
     *
     * @param value Positive integer value to calculate log2 for
     * @return Ceiling of log base 2 (minimum bits to represent value-1)
     * @throws AssertionError if value is not positive
     */
    object log2Up {
        def apply(value: BigInt): Int = {
            assert(value > 0,s"No negative value ($value) on ${this.getClass.getSimpleName}")
            (value - 1).bitLength
        }
    }
}